package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;







import javax.management.RuntimeErrorException;

import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
原题　
		Given a linked list, remove the nth node from the end of list and return its head.
	
	For example,
	
	   Given linked list: 1->2->3->4->5, and n = 2.
	
	   After removing the second node from the end, the linked list becomes 1->2->3->5.
	
	Note:
	Given n will always be valid.
	Try to do this in one pass. 
题目大意
	给定一个链表,删除第n个节点的列表并返回。
	例如,
	考虑到链表:1 - > 2 - > 3 - > 4 - > 5,n = 2。
	
	
	把第二个节点从结束后,链表变成1 - > 2 - > 3 - > 5。
	注意:
	给定n将永远有效。
	试着这样做一遍。 
解题思路
	
 * @Date 2017-09-26 16：36
 */
public class _019_Remove_Nth_Node_From_End_of_List {
	/**
	 * @My
	 * @param head
	 * @param n
	 * @return
	 */
    public ListNode removeNthFromEnd(ListNode head, int n) {
    	/**
    	 * 删除倒数第二个
    	 */
//    	ListNode p = head, pre = null;
//    	while (p.next != null) {
//    		pre = p;
//    		p = p.next;
//    	}
//    	ListNode next = pre.next;
//    	pre.val = next.val;
//    	pre.next = next.next;
//    	ListNode.traverse("结果", head);
//    	LogUtils.println("pre", pre.val+"");
    	
    	//计算总共几个
    	ListNode p = head;
    	int total = 0;
    	while (p != null) {
    		total++;
    		p = p.next;
    	}
    	if (total==n && n==1) {
    		return null;
    	} else if (total!=n && n==1) {
    		LogUtils.print("有执行到这吧");
    		p = head;
    		ListNode pre = null;
        	while (p.next != null) {
        		pre = p;
        		p = p.next;
        	}
        	pre.next = null;
    	} else {
	    	/**
	    	 * 删除倒数第n个
	    	 */
	    	p = head;
	    	while (p!=null && p.next != null) {
	    		ListNode startQuery = p;
	    		ListNode q = p;		//查找到的节点，查找到的前一个节点
	    		int count=1;
	    		while (q.next!=null) {
	    			q = q.next;
	    			if (count+1 == n) {
	    				break;
	    			}
	      			count++;
	    		}
	    		if ((q.next==null) && count+1==n) {
	    			//startQuery就是倒数第n个节点
	    			ListNode nextStart = startQuery.next;
	    			startQuery.val = nextStart.val;
	    			startQuery.next = nextStart.next;
	    		}
	    		if (q.next!=null && count>=n) { 	
	    		}
	    		p = p.next;	
	    	}
    	}
    	ListNode.traverse("", head);
        return head;
    }
    
	public static ListNode newLinkListOrdered() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(2);

		return root;
	}
    
	public static void main(String[] args) {
		_019_Remove_Nth_Node_From_End_of_List obj = new _019_Remove_Nth_Node_From_End_of_List();
		obj.removeNthFromEnd(ListNode.newLinkListOrdered(), 1);
	}

}
